#include<iostream>
using namespace std;
int add(int co[],int k)
{ 
	if(co[k]==0){
		co[k]=1;
		return k;
	}
	
	else{
		co[k]=0;
		return add(co,k-1);}
}

int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	int n;//zong
	
	cin>>n;
	long long CM[n+5];
	for(int i=1;i<=n;i++)
	{
		
		int m;//fen
		cin>>m;
		int mx=m-1;
		for(int i=2;i<=m-1;i++)
			mx=mx*(m-i);
		long long C[mx+50000];
		int a[m+5000];
		int co[m+5000];
		
		
		for(int u=1;u<=m;u++){
			cin>>a[u];
			
		}
		for(int u=1;u<=m+5;u++){
			co[u]=0;
			C[u]=0;
		}
		co[1]=1;
		//paint time
		int lt=m;//long
		int dl=1;;
		
		for(int q=1;q<=mx+1;q++)
		{
			int l1=1;
			int l0=0;
		
			if(lt==dl){
				lt=m-dl;
				dl++;
				for(int u=1;u<=m;u++){
					co[u]=0;
				}
				co[1]=1;
			}
			
			
			//paint001

			if(dl!=m)
			{
				if(co[lt]==1){
					int lk=add(co,lt);
					co[lk]=1;
					for(int l=lk+1;l>=m;l--)co[l]=0;
					
				}
				else{
					co[lt]++;
				}
			}
			
			if(q==(lt-dl)*(lt-dl-1)+1)
				lt--;
				
				
			
			//work
			for(int k=2;k<=m;k++){
				if(co[k]==1){
					if(a[k]==a[l1]){C[q]+=a[k];}
					else l1=k;

				}
				else if(co[k]==0){
					if(l0==0)l0=k;
					else{
						if(a[k]==a[l0]){
							C[q]+=a[k];
							
						}
						else l0=k;
					}
				}
			}
			
		}
		long long max=C[1];
		for(int i = 2;i<=m;i++)
		{
			
			if(C[i]>max)
				max=C[i];
		}
		CM[i]=max;
	}
	for(int i = 1;i<=n;i++)
	{
		cout<<CM[i]<<endl;
		
	}
	return 0;
}

